// 给定一个整数n，生成所有可能且有效的括号组合
// 
// 解题思路：回溯算法
// 为了生成的括号组合是有效的，回溯的时候，使用一个标记变量symbol来表示当前组合是否成对匹配
// 如果在当前组合中增加一个(,则symbol+1，如果增加一个)，则symbol-1，只有在symbol<n的时候才能增加(，在symbol>0的时候才能增加）
// 如果最终生成2*n的括号组合，并且symbol===0，则说明当前组合是有效的，将其加入到最终答案数组中
function generateParenthesis(n) {
    let result = []
    function backtracking(str, symbol, index) {
        if (index === 2 * n) {
            if (symbol === 0) {
                result.push(str)
            }
            return
        } 
        if (symbol < n) {
            backtracking(str + '(', symbol + 1, index + 1)
        }
        if (symbol > 0) {
            backtracking(str + ')', symbol - 1, index + 1)
        }
    } 
    backtracking('', 0, 0)
    return result
}

console.log(generateParenthesis(3))